package goleetcode

func queensAttacktheKing(queens [][]int, king []int) [][]int  {
	queen_pos := make(map[int]bool)
	for _, queen := range queens {
		x, y := queen[0], queen[1]
		queen_pos[x * 8 + y] = true
	}

	ans := [][]int{}
	for dx := -1; dx <= 1; dx++ {
		for dy := -1; dy <= 1; dy++ {
			if dx == 0 && dy == 0 {
				continue
			}
			// the king's location is kx, ky, the directions is dx, dy
			kx, ky := king[0] + dx, king[1] + dy
			for kx >= 0 && kx < 8 && ky >= 0 && ky < 8 {
				pos := kx * 8 + ky
				if _, ok := queen_pos[pos]; ok {
					ans = append(ans, []int{kx, ky})
					break
				}
				kx += dx
				ky += dy
			}
		}
	}
	return ans
}